/*

Archivo: "tree.h"

Implementación de un árbol binario de búsqueda genérico sin balancear.

Implementación: todos los sucesores y predecesores para los 3 traversals
están implementados en forma iterativa, así cómo también los
mínimos y máximos correspondientes, en base a estos se definen los iteradores.
Sirve cómo clase base para el árbol AVL.

Autor: Diego Luna

Primera versión: 5-6-2012

*/


#ifndef __TREE_H_INCLUDED
#define __TREE_H_INCLUDED


#include <iostream>
#include <cstdlib>
#include <typeinfo>
#include <cmath>

// Solo se compila en modo de pruebas.
#if (CONTAINER_DEBUG == 1)
#include <vector>
#include <algorithm>
#endif

#include "globals.h"
#include "bases.h"


// Tipos de iterador para el árbol.
#define IN_ORDER_ITERATOR DEFAULT_ITERATOR
#define PRE_ORDER_ITERATOR SECOND_ITERATOR
#define POST_ORDER_ITERATOR THIRD_ITERATOR


/* ========================= Binary_Search_Tree - Begin ========================== */
template <typename T>
class Binary_Search_Tree: public Base_Container<T>
{

public:

    // Iterador bidireccional para el árbol (In-Order).
    typedef Base_Iterator<T, IN_ORDER_ITERATOR> In_Order_Iterator;

    // Iterador bidireccional para el árbol (Pre-Order).
    typedef Base_Iterator<T, PRE_ORDER_ITERATOR> Pre_Order_Iterator;

    // Iterador bidireccional para el árbol (Post-Order).
    typedef Base_Iterator<T, POST_ORDER_ITERATOR> Post_Order_Iterator;

    // ++++++++++++++++++++++++ Constructores\Destructores - Begin +++++++++++++++++++++++++++++

    // Constructor.
    Binary_Search_Tree();

    // Constructor copia.
    Binary_Search_Tree(const Binary_Search_Tree&);

    // Destructor.
    virtual ~Binary_Search_Tree();

    // ++++++++++++++++++++++++ Constructores\Destructores - End +++++++++++++++++++++++++++++++


    // ++++++++++++++++++++++++ Métodos públicos - Begin +++++++++++++++++++++++++++++++++++++++

    // Devuelve el iterador al primer elemento (pre-order).
    Pre_Order_Iterator begin_pre_order() const;

    // Devuelve el iterador al siguiente al último elemento (pre-order).
    Pre_Order_Iterator end_pre_order() const;

    // Devuelve el iterador al anterior al primer elemento (pre-order).
    Pre_Order_Iterator rend_pre_order() const;

    // Devuelve el iterador al último elemento (pre-order).
    Pre_Order_Iterator rbegin_pre_order() const;

    // Devuelve el iterador al primer elemento (post-order).
    Post_Order_Iterator begin_post_order() const;

    // Devuelve el iterador al siguiente al último elemento (post-order).
    Post_Order_Iterator end_post_order() const;

    // Devuelve el iterador al anterior al primer elemento (post-order).
    Post_Order_Iterator rend_post_order() const;

    // Devuelve el iterador al último elemento (post-order).
    Post_Order_Iterator rbegin_post_order() const;

    // Devuelve la altura del árbol completo.
    size_t height() const;

// Solo se compila en modo de pruebas.
#if (CONTAINER_DEBUG == 1)

    // Imprime el traversal in-order, realmente no se
    // utiliza, es para comparar la salida del método
    // recursivo con el recorrido por iteradores.
    void print_in_order(std::ostream& oss);

    // Imprime el traversal pre-order, realmente no se
    // utiliza, es para comparar la salida del método
    // recursivo con el recorrido por iteradores.
    void print_pre_order(std::ostream& oss) const;

    // Imprime el traversal post-order, realmente no se
    // utiliza, es para comparar la salida del método
    // recursivo con el recorrido por iteradores.
    void print_post_order(std::ostream& oss) const;

    // Método que imprime el árbol en forma "gráfica" para elementos de un char (Muy ineficiente).
    void print_tree(std::ostream& oss) const;

#endif

    // ++++++++++++++++++++++++ Métodos públicos - End ++++++++++++++++++++++++++++++++++++++++++


    // ++++++++++++++++++++++++ Operadores - Begin ++++++++++++++++++++++++++++++++++++++++++++++

    // Operador de asignación.
    Binary_Search_Tree<T>& operator=(const Binary_Search_Tree&);

    // Operador de asignación (se sobreescribe para la asignación cuando se hace por
	// desreferencia de punteros a la clase base).
    virtual SetImplementation<T>& operator=(const SetImplementation<T>&);

    // ++++++++++++++++++++++++ Operadores - End ++++++++++++++++++++++++++++++++++++++++++++++++

protected:

    //-------------------------------------------
    // Clase nodo (protegida).

    class Tree_Node: public Base_Node<T>
    {

    public:

        //************************
        // Atributos de Tree_Node.

        // Nodo padre.
        Tree_Node* parent_;

        // Hijo izquierdo.
        Tree_Node* left_;

        // Hijo derecho.
        Tree_Node* right_;

        // Altura del nodo (solo se usa en AVL).
        size_t height_;
        //************************


        // ++++++++++++++++++++++++ Constructores\Destructores - Begin ++++++++++++++++++++++++
        // Constructor.
        Tree_Node(const Binary_Search_Tree<T>&, const T&);

        // Constructor copia.
        Tree_Node(const Tree_Node&);

        // Destructor.
        virtual ~Tree_Node();
        // ++++++++++++++++++++++++ Constructores\Destructores - End ++++++++++++++++++++++++++


        // ++++++++++++++++++++++++ Operadores - Begin ++++++++++++++++++++++++++++++++++++++++

        // Operador de asignación.
        Tree_Node& operator=(const Tree_Node&);

        // ++++++++++++++++++++++++ Operadores - End ++++++++++++++++++++++++++++++++++++++++++

    };

    //-------------------------------------------

    // ++++++++++++++++++++++++ Métodos protegidos - Begin ++++++++++++++++++++++++++++++++++++++

    // Métodos sobrescritos - Begin -------------------------------------------------------------

    // Devuelve un puntero al nodo con la clave indicada, devuelve NULL en caso de no encontrarse.
    virtual Base_Node<T>* find_node(const T&) const;

    // Agrega un elemento al contenedor devolviendo un puntero al nodo insertado o NULL si no se insertó.
    virtual Base_Node<T>* add_node(const T&, bool);

	// Elimina un elemento del contenedor.
	// Este método es llamado primero, en
	// caso de devolver "false" se llama al
	// que toma un nodo por parámetro.
    virtual bool delete_node_by_key(const T&, bool&);

    // Elimina un nodo del contenedor.
    virtual void delete_node(Base_Node<T>*);

    // Elimina todos los elementos del contenedor.
    virtual void delete_nodes();

    // Devuelve el sucesor de un nodo.
    virtual Base_Node<T>* next(Base_Node<T>*, Iterator_Type) const;

    // Devuelve el predecesor de un nodo.
    virtual Base_Node<T>* previous(Base_Node<T>*, Iterator_Type) const;

    // Devuelve el primer nodo para un tipo de iterador.
    virtual Base_Node<T>* first(Iterator_Type) const;

    // Devuelve el último nodo para un tipo de iterador.
    virtual Base_Node<T>* last(Iterator_Type) const;

    // Métodos sobrescritos - End ---------------------------------------------------------------


    // Elimina un nodo, asegurándose que no tiene hijos,
    // previamente estos fueron asignados a otros padres,
    // Es utilizado en el borrado de nodos.
    void delete_node_without_children(Tree_Node*);

    // Reemplaza un subárbol con otro subárbol.
    void transplant_node(Tree_Node*, Tree_Node*);

    // Devuelve la altura de un subárbol dada su raíz.
    virtual size_t height(Tree_Node*) const;

    // Inserta un nodo en el árbol con la clave dada,
    // en el subárbol especificado.
    virtual Tree_Node* insert_tree_node(const T&, bool);

    // Elimina un nodo del árbol.
    virtual void delete_tree_node(Tree_Node*);

    // ++++++++++++++++++++++++ Métodos protegidos - End ++++++++++++++++++++++++++++++++++++++++

private:

    //************************
    // Atributos de Binary_Search_Tree.

    // Raíz del árbol.
    Tree_Node* root_;

    //************************

    // ++++++++++++++++++++++++ Métodos privados - Begin ++++++++++++++++++++++++++++++++++++++

    // Devuelve la hoja que esta más a la izquierda (distinto al nodo más a la izquierda).
    Tree_Node* left_most_leaf(Tree_Node*) const;

    // Devuelve la hoja que esta más a la derecha (distinto al nodo más a la derecha).
    Tree_Node* right_most_leaf(Tree_Node*) const;

    //**** in-order traversal - Begin ****
    // Devuelve el nodo con la clave mínima (primero in-order).
    Tree_Node* in_order_minimun_node(Tree_Node* = NULL) const;

    // Devuelve el nodo con la clave máxima (último in-order).
    Tree_Node* in_order_maximun_node(Tree_Node* = NULL) const;

    // Devuelve el nodo siguiente al dado (in-order).
    Tree_Node* in_order_succesor_node(Tree_Node*) const;

    // Devuelve el nodo anterior al dado (in-order).
    Tree_Node* in_order_predecessor_node(Tree_Node*) const;
    //**** in-order traversal - End ****

    //**** pre-order traversal - Begin ****
    // Primero pre-order.
    Tree_Node* pre_order_minimun_node(Tree_Node* = NULL) const;

    // Último pre-order.
    Tree_Node* pre_order_maximun_node(Tree_Node* = NULL) const;

    // Devuelve el nodo siguiente al dado (pre-order).
    Tree_Node* pre_order_succesor_node(Tree_Node*) const;

    // Devuelve el nodo anterior al dado (pre-order).
    Tree_Node* pre_order_predecessor_node(Tree_Node*) const;
    //**** pre-order traversal - End ****

    //**** post-order traversal - Begin ****
    // Primero post-order.
    Tree_Node* post_order_minimun_node(Tree_Node* = NULL) const;

    // Último post-order.
    Tree_Node* post_order_maximun_node(Tree_Node* = NULL) const;

    // Devuelve el nodo siguiente al dado (post-order).
    Tree_Node* post_order_succesor_node(Tree_Node*) const;

    // Devuelve el nodo anterior al dado (post-order).
    Tree_Node* post_order_predecessor_node(Tree_Node*) const;
    //**** post-order traversal - End ****

    // Encontrar nodo con clave dada, devolviendo el nodo corespondiente,
    // comienza a buscar a partir del nodo indicado.
    Tree_Node* find_tree_node(Tree_Node*, const T&) const;

    // Elimina todos los nodos.
    void clear_tree_nodes();

    // Devuelve el nivel en el que se encuentra un nodo dado.
    size_t level(Tree_Node*) const;


// Solo se compila en modo de pruebas.
#if (CONTAINER_DEBUG == 1)

    // Este recorrido in-order no se usa es solo para comparar con los
    // recorridos con los sucesores y predecesores, los cuales son
    // utilizados por los iteradores, dada la simplicidad del método recursivo
    // sirve para comprobar la correctitud de los iteradores.
    void in_order_traversal_recursive(Tree_Node*, std::ostream&) const;

    // Este recorrido pre-order no se usa es solo para comparar con los
    // recorridos con los sucesores y predecesores, los cuales son
    // utilizados por los iteradores, dada la simplicidad del método recursivo
    // sirve para comprobar la correctitud de los iteradores.
    void pre_order_traversal_recursive(Tree_Node*, std::ostream&) const;

    // Este recorrido post-order no se usa es solo para comparar con los
    // recorridos con los sucesores y predecesores, los cuales son
    // utilizados por los iteradores, dada la simplicidad del método recursivo
    // sirve para comprobar la correctitud de los iteradores.
    void post_order_traversal_recursive(Tree_Node*, std::ostream&) const;

    // Método muy malo solo para poder ver el recorrido por niveles.
    void level_traversal_recursive(std::vector<Tree_Node*>& vecl, Tree_Node* p, size_t level) const;

#endif

    // ++++++++++++++++++++++++ Métodos privados - End +++++++++++++++++++++++++++++++++++++++++

};

/* ========================= Binary_Search_Tree - End ============================ */


// ++++++++++++++++++++++++ Constructores\Destructores [Binary_Search_Tree] - Begin ++++++++++++++++++++++++++++++++++++

// Constructor.
template <typename T>
Binary_Search_Tree<T>::Binary_Search_Tree():
    Base_Container<T>(), root_(NULL)
{
}

// Constructor copia.
template <typename T>
Binary_Search_Tree<T>::Binary_Search_Tree(const Binary_Search_Tree& bst):
    Base_Container<T>(bst), root_(NULL)
{
    *this = bst;
}

// Destructor.
template <typename T>
Binary_Search_Tree<T>::~Binary_Search_Tree()
{
    // Libero toda la memoria utilizada.
    Base_Container<T>::wipe();
}

// ++++++++++++++++++++++++ Constructores\Destructores [Binary_Search_Tree] - End ++++++++++++++++++++++++++++++++++++


// ++++++++++++++++++++++++ Constructores\Destructores [Binary_Search_Tree::Tree_Node] - Begin +++++++++++++++++++++++

// Constructor.
template <typename T>
Binary_Search_Tree<T>::Tree_Node::Tree_Node(const Binary_Search_Tree<T>& container, const T& key):
    Base_Node<T>(container, key), parent_(NULL), left_(NULL), right_(NULL)
{
}

// Constructor copia.
template <typename T>
Binary_Search_Tree<T>::Tree_Node::Tree_Node(const Tree_Node& tn):
    Base_Node<T>(tn), parent_(NULL), left_(NULL), right_(NULL)
{
    *this = tn;
}

// Destructor.
template <typename T>
Binary_Search_Tree<T>::Tree_Node::~Tree_Node()
{
    if (left_ != NULL)
        delete left_;

    if (right_ != NULL)
        delete right_;
}

// ++++++++++++++++++++++++ Constructores\Destructores [Binary_Search_Tree::Tree_Node] - End ++++++++++++++++++++++++


// ++++++++++++++++++++++++ Operadores [Binary_Search_Tree::Tree_Node] - Begin ++++++++++++++++++++++++++++++++++++++

// Operador de asignación.
template <typename T>
typename Binary_Search_Tree<T>::Tree_Node& Binary_Search_Tree<T>::Tree_Node::operator=(const Tree_Node& tn)
{
    // Verifico la autoasignación.
    if (&tn == this)
        return *this;

    // Borro el subárbol izquierdo actual.
    if (left_ != NULL)
    {
        delete left_;
        left_ = NULL;
    }

    // Borro el subárbol derecho actual.
    if (right_ != NULL)
    {
        delete right_;
        right_ = NULL;
    }

    // Llamo al operador de asignación de la clase base.
    Base_Node<T>::operator=(tn);

    // Copio el subárbol izquierdo.
    if (tn.left_ != NULL)
    {
        left_ = new Tree_Node(*(tn.left_));
        left_->parent_ = this;
    }

    // Copio el subárbol derecho.
    if (tn.right_ != NULL)
    {
        right_ = new Tree_Node(*(tn.right_));
        right_->parent_ = this;
    }

    // Retorno un referencia al propio nodo.
    return *this;
}

// ++++++++++++++++++++++++ Operadores [Binary_Search_Tree::Tree_Node] - End ++++++++++++++++++++++++++++++++++++++++++


// ++++++++++++++++++++++++ Métodos privados [Binary_Search_Tree] - Begin +++++++++++++++++++++++++++++++++++++++++++++

// Devuelve la hoja que esta más a la izquierda (distinto al nodo más a la izquierda).
template <typename T>
typename Binary_Search_Tree<T>::Tree_Node* Binary_Search_Tree<T>::left_most_leaf(Tree_Node* tn) const
{
    while (tn != NULL)
    {
        // Si tiene hijo izquierdo voy hacia ese hijo.
        if (tn->left_ != NULL)
            tn = tn->left_;
        // Si tiene hijo derecho voy hacia ese hijo.
        else if (tn->right_ != NULL)
            tn = tn->right_;
        else
            // No tiene hijos, es la hoja más a la izquierda.
            return tn;
    }

    // Si el puntero a nodo indicado es nulo,
    // devuelvo nulo.
    return tn;
}

// Devuelve la hoja que esta más a la derecha (distinto al nodo más a la derecha).
template <typename T>
typename Binary_Search_Tree<T>::Tree_Node* Binary_Search_Tree<T>::right_most_leaf(Tree_Node* tn) const
{
    while (tn != NULL)
    {
        // Si tiene hijo derecho voy hacia ese hijo.
        if (tn->right_ != NULL)
            tn = tn->right_;
        // Si tiene hijo izquierdo voy hacia ese hijo.
        else if (tn->left_ != NULL)
            tn = tn->left_;
        else
            // No tiene hijos, es la hoja más a la izquierda.
            return tn;
    }

    // Si el puntero a nodo indicado es nulo,
    // devuelvo nulo.
    return tn;
}

// Devuelve el nodo con la clave mínima.
template <typename T>
typename Binary_Search_Tree<T>::Tree_Node* Binary_Search_Tree<T>::in_order_minimun_node(Tree_Node* tn) const
{
    // Si el puntero a nodo indicado es nulo,
    // devuelvo el maximo de todo el árbol.
    if (tn == NULL)
    {
        if (root_ != NULL)
            tn = root_;
        else
            return NULL;
    }

    // El mínimo es el mínimo del subárbol izquierdo.
    while (tn->left_ != NULL)
        tn = tn->left_;

    // Retorno el último nodo que no tiene hijo izquierdo.
    return tn;
}

// Devuelve el nodo con la clave máxima.
template <typename T>
typename Binary_Search_Tree<T>::Tree_Node* Binary_Search_Tree<T>::in_order_maximun_node(Tree_Node* tn) const
{
    // Si el puntero a nodo indicado es nulo,
    // devuelvo el maximo de todo el árbol.
    if (tn == NULL)
    {
        if (root_ != NULL)
            tn = root_;
        else
            return NULL;
    }

    // El máximo es el máximo del subárbol derecho.
    while (tn->right_ != NULL)
        tn = tn->right_;

    // Retorno el último nodo que no tiene hijo derecho.
    return tn;
}

// Devuelve el nodo siguiente al dado (in-order).
template <typename T>
typename Binary_Search_Tree<T>::Tree_Node* Binary_Search_Tree<T>::in_order_succesor_node(Tree_Node* tn) const
{
    // Si el nodo es nulo no tiene sucesor.
    if (tn == NULL)
        return NULL;

    // Si tiene hijo derecho el sucesor es el mínimo del subárbol derecho.
    if (tn->right_ != NULL)
        return in_order_minimun_node(tn->right_);

    Tree_Node* parent = tn->parent_;

    // Si no tiene hijo derecho el predecesor es el ancestro mas cercano de tal modo que
    // el nodo dado es descendiente de su hijo izquierdo.
    while ((parent != NULL) && (tn == parent->right_))
    {
        tn = parent;
        parent = parent->parent_;
    }

    // El puntero a nodo retornado puede ser nulo (es el máximo).
    return parent;
}

// Devuelve el nodo anterior al dado (in-order).
template <typename T>
typename Binary_Search_Tree<T>::Tree_Node* Binary_Search_Tree<T>::in_order_predecessor_node(Tree_Node* tn) const
{
    // Si el nodo es nulo no tiene predecesor.
    if (tn == NULL)
        return NULL;

    // Si tiene hijo izquierdo el predecesor es el máximo del subárbol izquierdo.
    if (tn->left_ != NULL)
        return in_order_maximun_node(tn->left_);

    Tree_Node* parent = tn->parent_;

    // Si no tiene hijo izquierdo el predecesor es el ancestro mas cercano de tal modo que
    // el nodo dado es descendiente de su hijo derecho.
    while ((parent != NULL) && (tn == parent->left_))
    {
        tn = parent;
        parent = parent->parent_;
    }

    // El puntero a nodo retornado puede ser nulo (es el mínimo).
    return parent;
}

// Primero pre-order.
template <typename T>
typename Binary_Search_Tree<T>::Tree_Node* Binary_Search_Tree<T>::pre_order_minimun_node(Tree_Node* tn) const
{
    // Si el puntero a nodo indicado es nulo,
    // devuelvo el mínimo de todo el árbol.
    if (tn == NULL)
    {
        if (root_ != NULL)
            tn = root_;
        else
            return NULL;
    }

    // El primer nodo en el recorrido pre-order es la raíz.
    return tn;
}

// Último pre-order.
template <typename T>
typename Binary_Search_Tree<T>::Tree_Node* Binary_Search_Tree<T>::pre_order_maximun_node(Tree_Node* tn) const
{
    // Si el puntero a nodo indicado es nulo,
    // devuelvo el maximo de todo el árbol.
    if (tn == NULL)
    {
        if (root_ != NULL)
            tn = root_;
        else
            return NULL;
    }

    // El último nodo en un recorrido pre-order es el nodo hoja mas a la derecha.
    // Coincide con el máximo de un recorrido in-order.
    return right_most_leaf(tn);
}

// Devuelve el nodo siguiente al dado (pre-order).
template <typename T>
typename Binary_Search_Tree<T>::Tree_Node* Binary_Search_Tree<T>::pre_order_succesor_node(Tree_Node* tn) const
{
    // Si el nodo es nulo no tiene siguiente.
    if (tn == NULL)
        return NULL;

    // Si tiene hijo izquierdo este es el sucesor.
    if (tn->left_ != NULL)
        return tn->left_;

    // Si tiene hijo derecho este es el sucesor.
    if (tn->right_ != NULL)
        return tn->right_;

    // Puntero a nodo auxiliar.
    Tree_Node* parent = tn->parent_;

    // Si es hoja, el sucesor es el hijo derecho del ancestro
    // mas cercano que sea hijo izquierdo.
    while (parent != NULL)
    {
        if ((parent->left_ == tn) && (parent->right_ != NULL))
            return parent->right_;
        else
        {
            tn = parent;
            parent = tn->parent_;
        }
    }

    // No hay sucesor para el nodo dado.
    return NULL;
}

// Devuelve el nodo anterior al dado (pre-order).
template <typename T>
typename Binary_Search_Tree<T>::Tree_Node* Binary_Search_Tree<T>::pre_order_predecessor_node(Tree_Node* tn) const
{
    // Si el nodo es nulo o es la raíz no tiene siguiente.
    if ((tn == NULL) || (tn == root_))
        return NULL;

    // Si el nodo tiene hermano izquierdo el predecesor es el descendiente hoja
    // más a la derecha de ese hermano.
    if ((tn->parent_ != NULL) && (tn->parent_->right_ == tn) && (tn->parent_->left_ != NULL))
        return right_most_leaf(tn->parent_->left_);

    // en otro caso es el predecesor es el padre.
    return tn->parent_;
}

// Primero post-order.
template <typename T>
typename Binary_Search_Tree<T>::Tree_Node* Binary_Search_Tree<T>::post_order_minimun_node(Tree_Node* tn) const
{
    // Si el puntero a nodo indicado es nulo,
    // devuelvo el maximo de todo el árbol.
    if (tn == NULL)
    {
        if (root_ != NULL)
            tn = root_;
        else
            return NULL;
    }

    // Devuelvo la hoja que está mas a la izquierda.
    return left_most_leaf(tn);
}

// Último post-order.
template <typename T>
typename Binary_Search_Tree<T>::Tree_Node* Binary_Search_Tree<T>::post_order_maximun_node(Tree_Node* tn) const
{
    // Si el puntero a nodo indicado es nulo,
    // devuelvo el maximo de todo el árbol.
    if (tn == NULL)
    {
        if (root_ != NULL)
            tn = root_;
        else
            return NULL;
    }

    // El último nodo en el recorrido post-order es la raíz.
    return tn;
}

// Devuelve el nodo siguiente al dado (post-order).
template <typename T>
typename Binary_Search_Tree<T>::Tree_Node* Binary_Search_Tree<T>::post_order_succesor_node(Tree_Node* tn) const
{
    // Si el nodo es nulo o es la raíz no tiene sucesor.
    if ((tn == NULL) || (tn == root_))
        return NULL;

    // Si el nodo tiene hermano derecho el sucesor es el descendiente
    // más a la izquierda de ese hermano.
    if ((tn->parent_ != NULL) && (tn->parent_->left_ == tn) && (tn->parent_->right_ != NULL))
        return left_most_leaf(tn->parent_->right_);

    // en otro caso es el sucesor es el padre.
    return tn->parent_;
}

// Devuelve el nodo anterior al dado (post-order).
template <typename T>
typename Binary_Search_Tree<T>::Tree_Node* Binary_Search_Tree<T>::post_order_predecessor_node(Tree_Node* tn) const
{
    // Si el nodo es nulo no tiene siguiente.
    if (tn == NULL)
        return NULL;

    if (tn->right_ != NULL)
        return tn->right_ ;
    // Si el nodo tiene hijo izquierdo el predecesor es ese hijo.
    else if (tn->left_ != NULL)
        return tn->left_ ;
    // Sino, el predecesor es el ancestro más cercano que tiene hermano izquierdo,
    // es decir el primer ancestro que es hijo derecho y tiene hermano.
    else
    {
        while (tn->parent_ != NULL)
        {
            if ((tn->parent_->right_ == tn) && (tn->parent_->left_ != NULL))
                return tn->parent_->left_;
            else
                tn = tn->parent_;
        }

        // Sino, no tiene predecesor.
        return NULL;
    }
}

// Encontrar nodo con clave dada, devolviendo el nodo corespondiente,
// comienza a buscar a partir del nodo indicado.
template <typename T>
typename Binary_Search_Tree<T>::Tree_Node* Binary_Search_Tree<T>::find_tree_node(Tree_Node* tn, const T& k) const
{
    // Si el puntero al nodo raíz del subárbol dónde buscar es nulo o tiene como clave el
    // valor buscado, devuelvo este mismo puntero.
    if ((tn == NULL) || (tn->key_ == k))
        return tn;

    // Me muevo a izquierda o derecha según el valor de la clave buscada.
    while ((tn != NULL) && (tn->key_ != k))
    {
        if (k < tn->key_)
            tn = tn->left_;
        else
            tn = tn->right_;
    }

    // Retorno el puntero el nodo hallado (puede ser NULL).
    return tn;
}

// Elimina todos los nodos.
template <typename T>
void Binary_Search_Tree<T>::clear_tree_nodes()
{
    if (root_ != NULL)
    {
        delete root_;
        root_ = NULL;
    }
}

// Devuelve el nivel en el que se encuentra un nodo dado.
template <typename T>
size_t Binary_Search_Tree<T>::level(Tree_Node* tn) const
{
    if (tn == NULL)
        return 0;

    int l = 1;

    while (tn->parent_ != NULL)
        l++;

    return l;
}

// Solo se compila en modo de pruebas.
#if (CONTAINER_DEBUG == 1)

// Este recorrido in-order no se usa es solo para comparar con los
// recorridos con los sucesores y predecesores, los cuales son
// utilizados por los iteradores, dada la simplicidad del método recursivo
// sirve para comprobar la correctitud de los iteradores.
template <typename T>
void Binary_Search_Tree<T>::in_order_traversal_recursive(Tree_Node* p, std::ostream& oss) const
{
    if(p != NULL)
    {
        if(p->left_)
            in_order_traversal_recursive(p->left_, oss);

        oss << p->key_ << ' ';

        if(p->right_)
            in_order_traversal_recursive(p->right_, oss);
    }
    else
        return;
}

// Este recorrido pre-order no se usa es solo para comparar con los
// recorridos con los sucesores y predecesores, los cuales son
// utilizados por los iteradores, dada la simplicidad del método recursivo
// sirve para comprobar la correctitud de los iteradores.
template <typename T>
void Binary_Search_Tree<T>::pre_order_traversal_recursive(Tree_Node* p, std::ostream& oss) const
{
    if(p != NULL)
    {
        oss << p->key_ << ' ';

        if(p->left_)
            pre_order_traversal_recursive(p->left_, oss);

        if(p->right_)
            pre_order_traversal_recursive(p->right_, oss);
    }
    else
        return;
}

// Este recorrido post-order no se usa es solo para comparar con los
// recorridos con los sucesores y predecesores, los cuales son
// utilizados por los iteradores, dada la simplicidad del método recursivo
// sirve para comprobar la correctitud de los iteradores.
template <typename T>
void Binary_Search_Tree<T>::post_order_traversal_recursive(Tree_Node* p, std::ostream& oss) const
{
    if(p != NULL)
    {
        if(p->left_)
            post_order_traversal_recursive(p->left_, oss);

        if(p->right_)
            post_order_traversal_recursive(p->right_, oss);

        oss << p->key_ << ' ';
    }
    else
        return;
}

// Método muy ineficiente solo para obtener el recorrido por niveles, se usa en el "graficado" del árbol.
template <typename T>
void Binary_Search_Tree<T>::level_traversal_recursive(std::vector<Tree_Node*>& vecl, Tree_Node* p, size_t l) const
{
    if (l == 1)
        vecl.push_back(p);
    else if (!p)
    {
        for (int i = 1; i <= std::pow(float(2), int(l - 1)); i++)
            vecl.push_back(NULL);
    }
    else
    {
        level_traversal_recursive(vecl, p->left_, l - 1);
        level_traversal_recursive(vecl, p->right_, l - 1);
    }
}

#endif

// ++++++++++++++++++++++++ Métodos privados [Binary_Search_Tree] - End +++++++++++++++++++++++++++++++++++++++++++++++++


// ++++++++++++++++++++++++ Métodos protegidos [Binary_Search_Tree] - Begin +++++++++++++++++++++++++++++++++++++++++++++

// Métodos sobrescritos - Begin --------------------------------------------------------------

// Devuelve un puntero al nodo con la clave indicada, devuelve NULL en caso de no encontrarse.
template <typename T>
Base_Node<T>* Binary_Search_Tree<T>::find_node(const T& key) const
{
    return find_tree_node(root_, key);
}

// Agrega un elemento al contenedor devolviendo un puntero al nodo insertado o NULL si no se insertó.
template <typename T>
Base_Node<T>* Binary_Search_Tree<T>::add_node(const T& key, bool accept_repeated)
{
    return insert_tree_node(key, accept_repeated);
}

// Elimina un elemento del contenedor.
// Este método es llamado primero, en
// caso de devolver "false" se llama al
// que toma un nodo por parámetro.
template <typename T>
bool Binary_Search_Tree<T>::delete_node_by_key(const T&, bool&)
{
	return false;
}

// Elimina un nodo del contenedor.
template <typename T>
void Binary_Search_Tree<T>::delete_node(Base_Node<T>* n)
{
    Binary_Search_Tree<T>::Tree_Node* tn = static_cast<Binary_Search_Tree<T>::Tree_Node*>(n);

    delete_tree_node(tn);
}

// Elimina todos los elementos del contenedor.
template <typename T>
void Binary_Search_Tree<T>::delete_nodes()
{
    clear_tree_nodes();
}

// Devuelve el sucesor de un nodo.
template <typename T>
Base_Node<T>* Binary_Search_Tree<T>::next(Base_Node<T>* n, Iterator_Type itt) const
{
    Binary_Search_Tree<T>::Tree_Node* tn = static_cast<Binary_Search_Tree<T>::Tree_Node*>(n);

    switch (itt)
    {
    case IN_ORDER_ITERATOR:
        return in_order_succesor_node(tn);
    case PRE_ORDER_ITERATOR:
        return pre_order_succesor_node(tn);
    case POST_ORDER_ITERATOR:
        return post_order_succesor_node(tn);
    default:
        return in_order_succesor_node(tn);
    }
}

// Devuelve el predecesor de un nodo.
template <typename T>
Base_Node<T>* Binary_Search_Tree<T>::previous(Base_Node<T>* n, Iterator_Type itt) const
{
    Binary_Search_Tree<T>::Tree_Node* tn = static_cast<Binary_Search_Tree<T>::Tree_Node*>(n);

    switch (itt)
    {
    case IN_ORDER_ITERATOR:
        return in_order_predecessor_node(tn);
    case PRE_ORDER_ITERATOR:
        return pre_order_predecessor_node(tn);
    case POST_ORDER_ITERATOR:
        return post_order_predecessor_node(tn);
    default:
        return in_order_predecessor_node(tn);
    }
}

// Devuelve el primer nodo para un tipo de iterador.
template <typename T>
Base_Node<T>* Binary_Search_Tree<T>::first(Iterator_Type itt) const
{
    switch (itt)
    {
    case IN_ORDER_ITERATOR:
        return in_order_minimun_node();
    case PRE_ORDER_ITERATOR:
        return pre_order_minimun_node();
    case POST_ORDER_ITERATOR:
        return post_order_minimun_node();
    default:
        return in_order_minimun_node();
    }
}

// Devuelve el último nodo para un tipo de iterador.
template <typename T>
Base_Node<T>* Binary_Search_Tree<T>::last(Iterator_Type itt) const
{
    switch (itt)
    {
    case IN_ORDER_ITERATOR:
        return in_order_maximun_node();
    case PRE_ORDER_ITERATOR:
        return pre_order_maximun_node();
    case POST_ORDER_ITERATOR:
        return post_order_maximun_node();
    default:
        return in_order_maximun_node();
    }
}

// Métodos sobrescritos - End ----------------------------------------------------------------

// Elimina un nodo, asegurándose que no tiene hijos,
// previamente estos fueron asignados a otros padres,
// Es utilizado en el borrado de nodos.
template <typename T>
void Binary_Search_Tree<T>::delete_node_without_children(Tree_Node* tn)
{
    if (tn == NULL)
        return;

    tn->left_ = NULL;
    tn->right_ = NULL;

    delete tn;
}

// Reemplaza un subárbol con otro subárbol.
template <typename T>
void Binary_Search_Tree<T>::transplant_node(Tree_Node* tn, Tree_Node* ntn)
{
    // Si el árbol a reemplazar es nulo no hago nada.
    if (tn == NULL)
        return;

    // Reemplazo con el subárbol ntn al hijo correspondiente
    // del padre de tn.

    if (tn->parent_ == NULL)
        root_ = ntn;
    else if (tn == tn->parent_->left_)
        tn->parent_->left_ = ntn;
    else
        tn->parent_->right_ = ntn;

    // Reasigno el padre de ntn.
    if (ntn != NULL)
        ntn->parent_ = tn->parent_;
}

// Devuelve la altura de un subárbol dada su raíz.
template <typename T>
size_t Binary_Search_Tree<T>::height(Tree_Node* tn) const
{
    if (tn == NULL)
        return 0;
    else
        return 1 + std::max(height(tn->left_), height(tn->right_));
}

// Inserta un nodo en el árbol con la clave dada.
template <typename T>
typename Binary_Search_Tree<T>::Tree_Node* Binary_Search_Tree<T>::insert_tree_node(const T& k, bool accept_repeated)
{
    // Creo un nuevo nodo con la clave indicada.
    Tree_Node* tn = new Tree_Node(*this, k);

    // Si el árbol esta vacío, este nuevo nodo es la raíz.
    if(root_ == NULL)
        root_ = tn;
    else
    {
        // Sino, encuentro el nodo padre dónde insertar el nuevo nodo hijo.

        // Comienzo por la raíz del árbol.
        Tree_Node** curr = &root_;
        Tree_Node* parent = NULL;

        // Recorro el árbol hasta encontrar un nodo hijo faltante.
        while(*curr)
        {
            parent = (*curr);

            if ((!accept_repeated) && (tn->key_ == (*curr)->key_))
            {
                // Destruyo el nodo creado.
                delete tn;

                // Retorno NULL para indicar que la clave era repetida.
                return NULL;
            }
            else if(tn->key_ > (*curr)->key_)
                curr = &((*curr)->right_);
            else
                curr = &((*curr)->left_);
        }

        // Asigno el hijo del padre localizado.
        (*curr) = tn;

        // Asigno el nodo padre al nuevo nodo creado.
        tn->parent_ = parent;
    }

    // Retorno un puntero al nodo creado.
    return tn;
}

// Elimina un nodo del árbol.
template <typename T>
void Binary_Search_Tree<T>::delete_tree_node(Tree_Node* tn)
{
    // No hay nodo a eliminar.
    if (tn == NULL)
        return;

    // El nodo a eliminar no tiene hijo izquierdo.
    if (tn->left_ == NULL)
        // El subárbol derecho reemplaza al nodo que se borra.
        transplant_node(tn, tn->right_);
    // El nodo a eliminar no tiene hijo derecho.
    else if (tn->right_ == NULL)
        // El subárbol izquierdo reemplaza al nodo que se borra.
        transplant_node(tn, tn->left_);
    // El nodo a eliminar tiene dos hijos.
    else
    {
        // Encuentro el sucesor del nodo a borrar.
        // El nodo sucesor tendrá o un nodo (derecho) o ninguno,
        // lo uso para intercambiar y borrar.
        Tree_Node* min_tn = in_order_succesor_node(tn); //in_order_minimun_node(tn->right_);//

        // Si el sucesor no es hijo (derecho) del nodo a borrar,
        // es decir el sucesor está más profundo en el subárbol derecho.
        if (min_tn->parent_ != tn)
        {
            // Reemplazo el sucesor por su hijo derecho.
            transplant_node(min_tn, min_tn->right_);

            // El hijo derecho del nodo a borrar pasa a
            // ser hijo derecho del sucesor.
            min_tn->right_ = tn->right_;
            min_tn->right_->parent_ = min_tn;
        }

        // Reemplazo el nodo a borrar por el sucesor.
        transplant_node(tn, min_tn);

        // El hijo izquierdo del nodo a borrar pasa a
        // ser hijo izquierdo del sucesor.
        min_tn->left_ = tn->left_;
        min_tn->left_->parent_ = min_tn;
    }

    // Borro el nodo sin borrar sus hijos (ya no lo son).
    delete_node_without_children(tn);
}

// ++++++++++++++++++++++++ Métodos protegidos [Binary_Search_Tree] - End +++++++++++++++++++++++++++++++++++++++++++++++


// ++++++++++++++++++++++++ Métodos públicos [Binary_Search_Tree] - Begin +++++++++++++++++++++++++++++++++++++++++++++++

// Devuelve el iterador al primer elemento (pre-order).
template <typename T>
typename Binary_Search_Tree<T>::Pre_Order_Iterator Binary_Search_Tree<T>::begin_pre_order() const
{
    return Pre_Order_Iterator(*this, SN_BEGIN);
}

// Devuelve el iterador al siguiente al último elemento (pre-order).
template <typename T>
typename Binary_Search_Tree<T>::Pre_Order_Iterator Binary_Search_Tree<T>::end_pre_order() const
{
    return Pre_Order_Iterator(*this, SN_END);
}

// Devuelve el iterador al anterior al primer elemento (pre-order).
template <typename T>
typename Binary_Search_Tree<T>::Pre_Order_Iterator Binary_Search_Tree<T>::rend_pre_order() const
{
    return Pre_Order_Iterator(*this, SN_R_BEGIN);
}

// Devuelve el iterador al último elemento (pre-order).
template <typename T>
typename Binary_Search_Tree<T>::Pre_Order_Iterator Binary_Search_Tree<T>::rbegin_pre_order() const
{
    return Pre_Order_Iterator(*this, SN_R_END);
}

// Devuelve el iterador al primer elemento (post-order).
template <typename T>
typename Binary_Search_Tree<T>::Post_Order_Iterator Binary_Search_Tree<T>::begin_post_order() const
{
    return Post_Order_Iterator(*this, SN_BEGIN);
}

// Devuelve el iterador al siguiente al último elemento (post-order).
template <typename T>
typename Binary_Search_Tree<T>::Post_Order_Iterator Binary_Search_Tree<T>::end_post_order() const
{
    return Post_Order_Iterator(*this, SN_END);
}

// Devuelve el iterador al anterior al primer elemento (post-order).
template <typename T>
typename Binary_Search_Tree<T>::Post_Order_Iterator Binary_Search_Tree<T>::rend_post_order() const
{
    return Post_Order_Iterator(*this, SN_R_BEGIN);
}

// Devuelve el iterador al último elemento (post-order).
template <typename T>
typename Binary_Search_Tree<T>::Post_Order_Iterator Binary_Search_Tree<T>::rbegin_post_order() const
{
    return Post_Order_Iterator(*this, SN_R_END);
}

// Devuelve la altura del árbol completo.
template <typename T>
size_t Binary_Search_Tree<T>::height() const
{
    return height(root_);
}

// Solo se compila en modo de pruebas.
#if (CONTAINER_DEBUG == 1)

// Imprime el traversal in-order, realmente no se
// utiliza, es para comparar la salida del método
// recursivo con el recorrido por iteradores.
template <typename T>
void Binary_Search_Tree<T>::print_in_order(std::ostream& oss)
{
    // Imprimo usando el método recursivo.

    oss << std::endl << std::endl << "In-Order traversal recursive:" << std::endl;

    in_order_traversal_recursive(root_, oss);

    oss << std::endl << std::endl;


    // Imprimo usando iteradores, en forma creciente.

    oss << std::endl << std::endl << "In-Order traversal iterating forward:" << std::endl;

    for_each(Base_Container<T>::begin(), Base_Container<T>::end(), Iterator_Printer<T>(oss, " "));

    oss << std::endl << std::endl;


    // Imprimo usando iteradores, en forma decreciente.

    oss << std::endl << std::endl << "In-Order traversal iterating backward:" << std::endl;

    for_each(Base_Container<T>::rbegin(), Base_Container<T>::rend(), Iterator_Printer<T>(oss, " "));

    oss << std::endl << std::endl;
}

// Imprime el traversal pre-order, realmente no se
// utiliza, es para comparar la salida del método
// recursivo con el recorrido por iteradores.
template <typename T>
void Binary_Search_Tree<T>::print_pre_order(std::ostream& oss) const
{

    // Imprimo usando el método recursivo.

    oss << std::endl << std::endl << "Pre-Order traversal recursive:" << std::endl;

    pre_order_traversal_recursive(root_, oss);

    oss << std::endl << std::endl;


    // Imprimo usando iteradores, en forma creciente.

    oss << std::endl << std::endl << "Pre-Order traversal iterating forward:" << std::endl;

    for_each(begin_pre_order(), end_pre_order(), Iterator_Printer<T>(oss, " "));

    oss << std::endl << std::endl;


    // Imprimo usando iteradores, en forma decreciente.

    oss << std::endl << std::endl << "Pre-Order traversal iterating backward:" << std::endl;

    for_each(rbegin_pre_order(), rend_pre_order(), Iterator_Printer<T>(oss, " "));

    oss << std::endl << std::endl;
}

// Imprime el traversal post-order, realmente no se
// utiliza, es para comparar la salida del método
// recursivo con el recorrido por iteradores.
template <typename T>
void Binary_Search_Tree<T>::print_post_order(std::ostream& oss) const
{
    // Imprimo usando el método recursivo.

    oss << std::endl << std::endl << "Post-Order traversal recursive:" << std::endl;

    post_order_traversal_recursive(root_, oss);

    oss << std::endl << std::endl;

    // Imprimo usando iteradores, en forma creciente.

    oss << std::endl << std::endl << "Post-Order traversal iterating forward:" << std::endl;

    for_each(begin_post_order(), end_post_order(), Iterator_Printer<T>(oss, " "));

    oss << std::endl << std::endl;

    // Imprimo usando iteradores, en forma decreciente.

    oss << std::endl << std::endl << "Post-Order traversal iterating backward:" << std::endl;

    for_each(rbegin_post_order(), rend_post_order(), Iterator_Printer<T>(oss, " "));

    oss << std::endl << std::endl;
}

// Método que imprime el árbol en forma "gráfica" para elementos de un char (Muy ineficiente).
template <typename T>
void Binary_Search_Tree<T>::print_tree(std::ostream& oss) const
{
    size_t h = height();

    std::vector<Tree_Node*> vecl;

    int n, sm, sh, sp, sep;
    bool brother;


    for (size_t level = 1; level <= h; level++)
    {
        // Vacío el vector.
        vecl.clear();

        // Orden inverso para el nivel.
        n = h + 1 - level;

        // Obtengo los nodos del nivel.
        level_traversal_recursive(vecl, root_, level);

        // Separación entre hermanos.
        sh = (n >= 2)?(3*std::pow(float(2), n - 1) - 1):1;

        // Separación entre primos.
        sp = (n >= 2)?(3*std::pow(float(2), n - 1) - 1):3;

        // Separación del margen.
        sm = (n >= 2)?(3*std::pow(float(2), n - 2) - 2):0;

        // Imprimo la separación del margen.
		oss << std::string(sm, ' ');

        // La primera separación es entre nodos "hermanos".
        brother = true;

        // Imprimo los elementos y los espacios libres.
        for (size_t i = 0; i < vecl.size(); i++)
        {
            // Imprimo el elemento o el lugar vacío.
            if (vecl[i] != NULL)
                oss << vecl[i]->key_;
            else
                oss << ' ';

            // Separación entre "hermanos" o "primos".
            if (brother)
                sep = sh;
            else
                sep = sp;

            // Imprimo la separación entre nodos o los saltos de líneas.
            if (i < (vecl.size() - 1))
				oss << std::string(sep, ' ');
            else if (level != h)
                oss << std::endl << std::endl;
            else
                oss << std::endl;

            // cambio el tipo de separación para el próximo nodo.
            brother = !brother;
        }
    }
}

#endif

// ++++++++++++++++++++++++ Métodos públicos [Binary_Search_Tree] - End ++++++++++++++++++++++++++++++++++++++++++++++++


// ++++++++++++++++++++++++ Operadores [Binary_Search_Tree] - Begin ++++++++++++++++++++++++++++++++++++++++++++++++++++

// Operador de asignación.
template <typename T>
Binary_Search_Tree<T>& Binary_Search_Tree<T>::operator=(const Binary_Search_Tree& bst)
{
    // Verifico la autoasignación.
    if (&bst == this)
        return *this;

    // Llamo al operador de asignación de la clase base.
    Base_Container<T>::operator=(bst);

    // Copio el árbol desde la raíz.
    if (bst.root_ != NULL)
        root_ = new Tree_Node(*bst.root_);

    // Devuelvo una referencia al propio árbol.
    return *this;
}

// Operador de asignación (se sobreescribe para la asignación cuando se hace por
// desreferencia de punteros a la clase base).
template <typename T>
SetImplementation<T>& Binary_Search_Tree<T>::operator=(const SetImplementation<T>& setimpl)
{
	if (typeid(setimpl) != typeid(*this))
		return SetImplementation<T>::operator=(setimpl);
	else
		return operator=(static_cast<const Binary_Search_Tree<T>& >(setimpl));
}

// ++++++++++++++++++++++++ Operadores [Binary_Search_Tree] - End ++++++++++++++++++++++++++++++++++++++++++++++++++++++

#endif
